public class BinarySearchTree {

    //树的节点
    static class TreeNode{
        public int val;

        public TreeNode left;

        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root = null;

    //搜索一个val
    public boolean search(int val){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val > val){
                cur = cur.left;
            }else if(cur.val < val){
                cur = cur.right;
            }else {
                return true;
            }
        }
        return false;
    }

    //插入一个节点
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        //根为空，说明树为空  直接将根指向新插入的节点
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        //寻找要插入的位置
        while(cur != null){
            parent = cur;
            //如果当前节点值大
            if(cur.val > val){
                //往左走
                cur = cur.left;
            }else if (cur.val < val){
                //当前节点小  往右走
                cur = cur.right;
            }else {

                //二叉搜索树中不能有重复的值
                return false;
            }
        }

        //再比较父节点和要插入节点的值
        if(parent.val < val){
            parent.right = node;
        }else {
            parent.left = node;
        }
        return true;
    }

    //删除一个节点
    public void remove(int val){

        //定义当前节点
        TreeNode cur = root;
        //记录当前节点的父节点
        TreeNode parent = null;

        //找到要删除节点的位置
        while(cur != null){
            if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else {
                removeNode(parent, cur);
                return;
            }
        }
    }

    //节点删除的操作  封装了一下  因为要传两个参数
    private void removeNode(TreeNode parent, TreeNode cur){

        //1.当前节点没有左孩子
        if(cur.left == null){
            //当前节点是根节点
            if(cur == root){
                //直接将根节点指向当前节点的右孩子
                root = cur.right;
            }else if(cur == parent.left){
                //当前节点是父节点的左孩子
                //那么删除当前节点只需要  将父节点的左孩子指向当前节点的左孩子
                parent.left = cur.right;
            }else {
                //当前节点是父节点的右孩子
                //那么删除当前节点只需要  将父节点的右孩子指向当前节点的右孩子
                parent.right = cur.right;
            }

            //当前节点没有右孩子
        }else if(cur.right == null){

            //并且当前节点是根节点
            if(cur == root){
                //直接将根节点指向当前节点的左孩子
                root = cur.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //当前节点既有左孩子  又有右孩子
            TreeNode targetParent = cur;
            //记录当前节点的右孩子
            TreeNode target = cur.right;

            //找到当前节点右子树的最左节点
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }

            //这个节点就是要替换成当前节点的节点
            //直接将这个目标节点的值赋给当前节点
            cur.val = target.val;

            //再判断这个节点是左孩子还是右孩子
            if(target == targetParent.left){
                //如果是左孩子
                //直接将这个节点的父节点的左孩子指向这个节点的右孩子
                targetParent.left = target.right;
            }else {
                //如果是右孩子
                //直接将这个节点的父节点的右孩子指向这个节点的右孩子
                targetParent.right = target.right;
            }
        }
    }

}
